#include "main/utils.h"
using namespace std;

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
      int n = quality.size();
      vector<int> h(n, 0);
      iota(h.begin(), h.end(), 0);
      sort(h.begin(), h.end(), [&](int a, int b) {
          return wage[a] * quality[b] < wage[b] * quality[a];
          });

      double min_totalc = 1e9;
      double totalq = 0.0;
      priority_queue<int, vector<int>, less<int>> queue;
      for (int i = 0; i < k - 1; ++i) {
        totalq += quality[h[i]];
        queue.push(quality[h[i]]);
      }
      for (int i = k - 1; i < n; ++i) {
        int idx = h[i];
        totalq += quality[idx];
        queue.push(quality[idx]);
        double totalc = totalq * wage[idx] / quality[idx];
        min_totalc = min(totalc, min_totalc);
        totalq -= queue.top();
        queue.pop();
      }
      return min_totalc;
    }
};

int main() {
  vector<int> quality = {10, 20, 5};
  vector<int> wage = {70, 50, 30};
  int k = 2;
  Solution su;
  cout << su.mincostToHireWorkers(quality, wage, k) << endl;

  return 0;
}
